class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        jobs.sort(reverse=True)
        l = jobs[0]
        r = sum(jobs)
        ans = 0
        while l <= r:
            mid = (l + r) // 2
            if self.check(mid, jobs, k):
                r = mid - 1
                ans = mid
            else:
                l = mid + 1
        return ans

    def check(self, t, jobs, k):
        workers = [0] * k
        return self.dfs(t, jobs, workers, 0)

    def dfs(self, t, jobs, workers, i):
        if i == len(jobs):
            return True
        for j in range(len(workers)):
            if workers[j] + jobs[i] <= t:
                workers[j] += jobs[i]
                if self.dfs(t, jobs, workers, i + 1):
                    return True
                workers[j] -= jobs[i]
            if workers[j] == 0 or workers[j] + jobs[i] == t:
                break
        return False